package q329_longestIncreasingPath;

public class Solution {
    int[][] memo;
    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    /*
    这是一个记忆化搜索的典型案例：
    首先对于一个图中需要寻找最长递增的一条路线，其开始的位置和终止的位置都是不确定的
    因此必然需要从每一个点出发去寻找 但这就导致有些之前已经算过的点没有被利用
    例如我们计算了从1号点出发寻找的最长路径长度 从二号点出发 经过一号点时 就可以不用再重新dfs
    而是直接利用一号点计算的结果 所以定义一个memo矩阵 来记录每个点计算的最长路径
     */
    public int longestIncreasingPath(int[][] matrix) {
        memo = new int[matrix.length][matrix[0].length];
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ans = Math.max(ans, dfs(i, j, matrix));
            }
        }
        return ans;
    }

    private int dfs(int i, int j, int[][] matrix) {
        // 如果不为0 代表这个点的最长路径已经被计算过了
        if (memo[i][j] != 0) return memo[i][j];
        // 否则就要从这个点开始计算 先+1
        ++memo[i][j];

        for (int[] dir : dirs) {
            int next_i = i + dir[0], next_j = j + dir[1];
            if (next_i >= 0 && next_i < matrix.length && next_j >= 0 && next_j < matrix[0].length && matrix[next_i][next_j] > matrix[i][j]) {
                memo[i][j] = Math.max(memo[i][j], dfs(next_i, next_j, matrix) + 1);
            }
        }
        return memo[i][j];
    }
}
